package com.sunny.l6;

import java.util.*;

public class Solution {

//    public static void main(String[] args) {
//
//        TreeNode root = new TreeNode(1);
//
//        TreeNode l = new TreeNode(2);
//        root.right = l;
//
//        Solution solution = new Solution();
//        ArrayList<Integer> a = solution.postorderTraversal(root);
//
//        a.forEach(System.out::print);
//    }

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        ArrayList<Integer> res = new ArrayList<>();
        Map<TreeNode,Boolean> used = new HashMap<>();

        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (null != p) {
            stack.push(p);
            p = p.left;
        }

        while (!stack.isEmpty()){

            TreeNode tmpNode = stack.peek();
            if(null != tmpNode.right && !used.containsKey(tmpNode)) {
                used.put(tmpNode, true);
                tmpNode = tmpNode.right;
                while (null != tmpNode){
                    stack.push(tmpNode);
                    tmpNode = tmpNode.left;
                }
            }else{
                stack.pop();
                res.add(tmpNode.val);
            }

        }

        return res;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}